Timetabling is a combinatorial optimization problem. The common examples of timetabling include school timetabling, sport game timetabling and transportation timetabling. The timetabling as a highly constrained and complex problem has been attracting the attention of the research community across Artificial Intelligence (AI) and Operational Research (OR) for more than four decades and still been heavily investigated as more and more experiences have been collected by the application of new technologies.
Various techniques have been employed for solving a wide range of timetabling problems. For example, graph coloring, integer programming and linear programming have been widely studied in the early days. However, these simple and easily implemented techniques are impractical for complex timetabling problems.
More lately, timetabling problems have been tackled by constraint programming and heuristics technologies such as Tabu Search, Simulated Anealing and Knowledge Based System approach. However, the timetabling problems are so complex that exhaustive search is often computationally intractable, thus the existing techniques and systems based upon a single and simple heuristic or algorithm often fail to provide optimal or near-optimal solutions.
Genetic algorithms have also been applied to timetabling problems. Briefly, the Genetic algorithms (GA) are based upon the principles of natural selection and evolution. In a GA system, solution of a problem is encoded in an artificial chromosome. Each unit of the chromosome, known as a gene, is a variable with a defined range of values. Genetic algorithms operate on a population of encoded solutions or chromosomes in a selection-reproduction evolution cycle. The first generation of a selection-reproduction evolution cycle consists of a number of randomly generated chromosomes, which are then selected according to a fitness quality. Selected fit members of the first generation are put into a mating pool for reproduction from which a new generation is derived by combining (crossover) or altering (mutating) genes among individuals within the population. The selection-reproduction evolution cycle repeats until an optimal solution is found or after a number of predetermined evolution cycles.
However, existing GA-based timetabling systems are not able to solve large and complex timetabling problems with a very large number of activities and/or too complex resource constraints. The reason may be that for a successful application of genetic algorithms, one of the conditions is that the chromosomes encoding the solutions must be within a manageable length. In most of cases, the number of genes in a chromosome must be within fifty to one hundred, or at most a few hundreds. However, the number of activities to be scheduled in an education institute can easily reach several thousands, wherein each activity may require multiple resources. Thus, each chromosome may contain a few thousand genes, sometimes even more than ten thousand genes. Therefore, the chromosomes required to encode a large and complex timetabling are too lengthy for a GA-based searching engine to manage.
Recently ant colony optimization (ACO) has been utilized for solving timetabling problems. Briefly, the ant colony optimization (ACO) algorithm is a meta-heuristic technique using of simple cooperating agents called artificial ants. The ants iteratively construct candidate solution to a combinatorial optimization problem. An individual ant constructs a candidate solution by starting with an empty solution, and then iteratively adds solution components, which is selected using local search heuristic and pheromone deposited, if any, until a complete candidate solution is generated. After the solution construction is completed, the ants give feedback on the solutions they have constructed by depositing pheromone on searching paths using global pheromone updating rules. Solution components that are better or partially better are used by more ants and therefore receive a higher amount of pheromone until an optimal solution is found.
M. Dorigo, and V. Maniezzo and A. Coloni initially deduced the ACO meta-heuristic in ant colony optimization by studying the behavior of real ants in establishing the shortest path from their colony to feeding sources and back. See, Dorigo et al., Ant System: Optimization by a Colony of Cooperating Agents, IEEE Trans. Sys., Man, Cybernetics 26(1): 29-41 (1996). Generally, an ACO meta-heuristic consists of three problem-solving steps. First, the optimization problem is defined into a graph. Second, a local searching heuristic is applied to select the next node for an ant to move to until the ant completes its solution construction. Finally, when all ants have constructed a complete solution, global pheromone updating rules are applied to update pheromone on links of visited nodes. The cooperating agents defined by M. Dorigo, et al, are basically pheromone-based cooperating agents, which communicate each other in the solution search cycles by utilizing the density of the pheromone deposited on the searching path.
The ACO meta-heuristic has been applied to solve various combinatorial optimization problems such as the traveling salesman problem (TSP) and tour routing problems. Although the ACO meta-heuristic with pheromone-based agents has been proven useful for solving some combinatorial optimization problems (COPs), it has not been successfully used in solving large and complex COPs, such as large and complex timetabling problems. The reason why the ACO meta-heuristic using pheromone based cooperating agents has not been successful in timetabling is because the solution searching method using pheromone based agents is simply based upon pheromone updating rules and formula, which are not sufficient to cope with the sizable solution space and multiple constraints imposed.
Recently, efforts have been made to solve scheduling problems using ACO or ant algorithms. For example, Socha et al. tried to use ant algorithms to solve university timetabling problem. See, Socha et al., “Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art”, Proceedings of EvoCOP 2003-3rd European Workshop on Evolutionary Computation in Combinatorial Optimization, Springer-Verlag, vol. 2611, p334-345. (url=http://citeseer.istpsu.edu/socha03ant.html). However, since the searching agents used by Socha at el. were simple pheromone-based cooperating agents, the system developed by them could only solve small and simplified timetabling problem. Since the pheromone, which is the medium used for communication among cooperating agents, contains very limited information, agents must be given more intelligence in order to enable them to solve large and complex COPs, such as large and complex timetabling problems.
Besides the pheromone-based agents, currently autonomous agents and multi-agent systems (AAMAS) become one of the prominent and attractive technologies in Al and computer science community. The technologies, methods, and theories of the agents and multi-agent systems are a conceptual paradigm for analyzing problems, currently contributing to many diverse domains such as information retrieval, user interfaces, electronic commerce, robotics, computer mediated collaboration, computer games, education and training, ubiquitous computing, and social simulation. However, they are still very new and emerging technology, not ready for dealing with complexity and interactivity of the large timetabling problems. In particular, the decision-making and optimization methodologies of the autonomous agents and multi-agent systems, such as trust and utility manipulations, are still in research stage, not mature enough for industrial applications although efforts have been made to develop prototype systems which utilize autonomous agents to solve various combinatory optimization problems.
Therefore, there is an existing need for a method and system for complex timetabling problems. This invention satisfies this need by providing a method and system for timetabling that uses pheromone and hybrid heuristics based cooperating agents. The method and system of the present invention overcomes the limitations of the existing ACO method and ant systems in solving large complex timetabling problems by using more intelligent cooperating agents that combine pheromone density manipulation with hybrid heuristics. The intelligent cooperating agents could be able to solve large and complex timetabling problems as well as to optimize solutions by satisfying multiple constraints imposed and meeting multiple optimization criteria. Other advantages of this invention will be apparent with reference to the detailed description.